Sean dos cadenas sobre el alfabeto Α

ω=a ₁,a ₂,... a _n y η=b ₁,b ₂,... b _m a _i,b _j ∈ Α

Longitud de una cadena:

|ω| denota la longitud de la cadena ω

Igualdad

ω=η si |ω|=|η| y (∀i: i 1 ≤ i ≤ |ω|: a _i=b _i)

Reversa

ω^R denota la reversa de la cadena ω
ω^R = a _n, a _n-1,... a ₂, a ₁

Concatenación

ω⋅η denota la concatenación, la cual consiste en la en la secuencia de símbolos de ω seguidos de los de η
ω⋅η = a ₁,a ₂,... a _n, b ₁,b ₂,... b _m

Exponenciacion

ω^k denota la concatenación de ω con si misma k-1 veces
ω⁰ = ε, la Cadena vacía
ω^k=ω^k-1⋅ω

Ejemplos

A continuación se calculan algunas operaciones para las cadenas α₁, α₂, α₃, y α₄ del ejemplo dado en la definición de cadenas:

Longitud

• |α₁| = |0101| = 4
• |α₄| = |ε| = 0

Reversa:

• α₁^R = 1010

Concatenación

• α₁⋅α₂ = 01011111
• α₂⋅α₄ = 1111
• α₂⋅α₂ = 11111111

Potencia

• α₂³ = α₂⋅α₂⋅α₂ = 111111111111
• α₁⁴ = 0101010101010101